#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <climits>
#include <memory>

using namespace std;

// 二叉树的右视图
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

class Solution
{
public:
    vector<int> rightSideView(TreeNode *root)
    {
        if (root == nullptr)
            return {};
        vector<int> ans;
        queue<TreeNode *> q;
        q.push(root);
        while (q.size())
        {
            int size = q.size();
            while (size--)
            {
                TreeNode *node = q.front();
                if (node->left)
                    q.push(node->left);
                if (node->right)
                    q.push(node->right);
                if (size == 0)
                {
                    ans.push_back(q.front()->val);
                }
                q.pop();
            }
        }

        return ans;
    }
};

// 爬楼梯
class Solution
{
public:
    int climbStairs(int n)
    {
        if (n <= 2)
            return n;
        int n1 = 1, n2 = 2, n3;
        for (int i = 0; i < n - 2; i++)
        {
            n3 = n1 + n2;
            n1 = n2;
            n2 = n3;
        }
        return n3;
    }
};

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// 翻转链表
class Solution
{
public:
    ListNode *reverseList(ListNode *head)
    {
        if (head == nullptr || head->next == nullptr)
            return head;
        ListNode *newhead = nullptr, *cur = head;
        while (cur)
        {
            ListNode *next = cur->next;
            cur->next = newhead;
            newhead = cur;
            cur = next;
        }

        return newhead;
    }
};

// 回文子串
class Solution
{
public:
    int countSubstrings(string s)
    {
        // dp[i][j]表示以i为起始位置j为结束位置的子串是否为回文子串
        int n = s.size(), ans = 0;
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
                if (dp[i][j])
                    ans++;
            }
        }

        return ans;
    }
};

// 最长回文子串
class Solution
{
public:
    string longestPalindrome(string s)
    {
        int n = s.size(), begin = 0, len = 0;
        for (int i = 0; i < n; i++)
        {
            int left = i, right = i + 1;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                left--;
                right++;
            }
            if (right - left - 1 > len)
            {
                len = right - left - 1;
                begin = left + 1;
            }

            left = i, right = i;
            while (left >= 0 && right < n && s[left] == s[right])
            {
                left--;
                right++;
            }
            if (right - left - 1 > len)
            {
                len = right - left - 1;
                begin = left + 1;
            }
        }

        return s.substr(begin, len);
    }
};

class Solution
{
public:
    string longestPalindrome(string s)
    {
        // dp[i][j]表示以i为起始位置j为结束位置的子串是否为回文子串
        // s[i] != s[j]  dp[i][j] = false
        // s[i] == s[j] i == j dp[i][j] = true
        // i + 1 == j  dp[i][j] = true
        // i + 1 < j  dp[i][j] = dp[i+1][j-1]
        // i 要从上往下,j从前往后
        int n = s.size(), len = 0, begin = 0;
        vector<vector<bool>> dp(n, vector<bool>(n));
        for (int i = n - 1; i >= 0; i--)
        {
            for (int j = i; j < n; j++)
            {
                if (s[i] == s[j])
                {
                    dp[i][j] = i + 1 < j ? dp[i + 1][j - 1] : true;
                }
                // if(s[i] != s[j]) dp[i][j] = false;
                // else if(i + 1 < j) dp[i][j] = dp[i+1][j-1];
                // else dp[i][j] = true;
                // 长度大于最大长度且为true
                // 更新最大长度和起始位置
                if (dp[i][j] && j - i + 1 > len)
                {
                    len = j - i + 1;
                    begin = i;
                }
            }
        }

        return s.substr(begin, len);
    }
};
